1. Field of the Invention
The present invention relates to technology for compressing image data, particularly relates to lossless compression for a multivalued input image.
2. Description of the Related Art
As the quantity of image data is generally enormous, image data is often compressed to reduce the quantity in communication, storage and others. A method of compressing image data is roughly classified into two types of a lossless coding method and a lossy coding method. In the latter case, visual degradation may occur in a decoded image depending upon compression ratio.
Recently, for a typical image described in page description language (PDL), an image generated by a computer (hereinafter generically called a computer graphic (CG) image) increases. As these images include no noise component caused in scanning, the degradation of image quality by lossy coding is remarkable at an edge.
In lossy coding called a baseline process defined in a joint photographic coding experts group (JPEG) (refer to p. 160 to 182 of xe2x80x9cInterfacexe2x80x9d, December 1991 issue) which is a standard of image coding, after an image is converted to a frequency component using discrete cosine transform (DCT), it is quantized. JPEG is effective in a scanned image the energy of which concentrates on a low-frequency component. However, the degradation occurs in an image acquired by decoding a CG image including many high-frequency components. For an example of the degradation of image quality, mosquito noise caused in the vicinity of an edge and block noise caused between blocks can be given.
In the meantime, lossless coding, in which the same decoded image as an input image is acquired, can avoid the degradation of image quality. For an example of technology particularly related to a CG image in conventional type lossless coding, proposal disclosed in Japanese published unexamined patent application No. Hei 9-224253 will be described below. The above conventional type utilizes the characteristics of a CG image that a prediction based upon neighbor pixels often hit and uses a hit one of plural predictions as a code.
Conventional type image coding device and image decoding device are respectively shown in upper and lower halves in FIG. 16. As shown in FIG. 16, a reference number 10 denotes an image input unit, 20 denotes a first predictor, 21 denotes a second predictor, 30 denotes a prediction error calculator, 31 denotes a prediction error adder, 40 and 41 denote a selector, 50 denotes an encoder, 51 denotes a decoder, 60 denotes a code output unit, 70 denotes a code input unit, 80 denotes an image output unit, 100 denotes image data, 110 denotes prediction value data, 111 denotes control data, 120 denotes prediction error data, 130 denotes prediction result data and 140 denotes code data.
Each unit shown in FIG. 16 will be described below. The image coding device shown in the upper half in FIG. 16 is made up as follows. The image input unit 10 receives an image input from an external device and respectively sends it to the first and second predictors 20 and 21 and the prediction error calculator 30 as image data 100. The first and second predictors 20 and 21 predict the value of a target pixel based upon the image data 100 according to respective predetermined methods and send it to the selector 40 as predicted value data 110. The prediction error calculator 30 predicts the value of the target pixel based upon the image data 100 according to a predetermined method, subtracts the predicted value from the actual value of the target pixel and sends the value to the selector 40 as prediction error data 120. The selector 40 detects based upon the image data 100 and the predicted value data 110 whether the prediction is coincident at the target pixel or not. If there is one or more hit predictors, the selector converts the identification number of the hit predictor to prediction result data 130 and sends it to the encoder 50. If not, the prediction error data 120. The encoder 50 encodes the prediction result data 130 using a predetermined entropy coding method and sends it to the code output unit 60 as code data 140. The code output unit 60 outputs the code data 140 to an external device as an output code.
Next, each unit of the image decoding device shown in the lower half in FIG. 16 will be described. The same number is allocated to the same each unit as that in the image coding device and the description is omitted. The code input unit 70 receives a code input from an external device and sends it to the decoder 51 as code data 140. The decoder 51 decodes the code data 140 according to a decoding method corresponding to the coding method used in the encoder 60 and sends it to the selector 41 as prediction result data 130. The selector 41 sends control data 111 to the corresponding predictor if the prediction result data 130 represents the identification number of the predictor and instructs the predictor to output image data 100. The selector also sends the prediction error data 120 to the prediction error adder 31 if the contents of the prediction result data 130 show an error. The prediction error adder 31 predicts the value of a target pixel according to the same method as that of the prediction error calculator 30, adds the prediction error data 120 to the predicted value and sends it to the image output unit 80 as image data 100. The image output unit 80 outputs the image data 100 to an external device to as an output image.
The operation based upon the above configuration will be described below. FIGS. 17 and 18 are flowcharts showing the operation of conventional type image coding/decoding device. The operation of the conventional type will be described below.
First, referring to FIG. 17, coding processing will be described. In S10, the image input unit 10 inputs an image. In S20, the first and second predictors 20 and 21 predict the value of a target pixel based upon image data 100 and simultaneously, the prediction error calculator 30 calculates an error of a predicted value according to a predetermined method. In S30, the selector 40 sends the identification number of the hit predictor or a prediction error to the encoder 50 as prediction result data 130. In S50, the encoder 50 applies predetermined coding to the prediction result data 130. In S60, if input image data is finished, coding processing is terminated and if not, the processing proceeds to S10.
Next, decoding processing will be described referring to FIG. 18. In S110, the code input unit 70 inputs a code. In S120, the decoder 51 executes decoding processing which is equivalent to processing reverse to coding processing executed by the encoder 50 and generates prediction result data 130. In S130, the selector 41 sends control data 111 to either of the first or second predictor 20 or 21 having the following identification number when the prediction result data 130 represents the identification number of the predictor. If the prediction result data 130 represents a prediction error, the selector 41 also sends the prediction error to the prediction error adder 31 as prediction error data 120. In S21, if there is one or more hit prediction, either of the first or second predictor 20 or 21 which receives the control data 111 executes predetermined prediction and generates image data 100. If there is not, the prediction error adder 31 adds prediction error data 120 to a predicted value acquired by the similar prediction to the prediction error calculator 30 and generates image data 100. In S140, the image output unit 80 outputs the image data 100 to an external device. In S150, when input code data is finished, decoding processing is terminated and if not, the processing proceeds to S110.
Of the above operation, the selection of the predictor in S30 is performed according to a predetermined priority or suited one as the rank order of the predictors in a second embodiment of the above Japanese published unexamined patent application No. Hei 9-224253. Also, for an example of the encoder 50, run length coding applied to the identification number of the first predictor 20 is described.
Next, the problem of the conventional type will be described. In prior art, priority is given to the selection of the predictor fixedly or suitably. In any case, as the predictors are related in precedence order, the above order is generically called priority. According to prior art, as priority is known before prediction, the processing can be efficiently executed if the predictor having higher priority executes ahead. For example, in the case of sequential processing by software, efficient processing is also enabled. Conversely, if priority is not suitable, the quantity of codes may be increased. An example of the above will be given below.
An example that fixed priority is used and run length coding is executed as an encoder is given. In this case, as runs are generally longer when the selection of a predictor is repeated, the quantity of codes is reduced.
FIG. 19A to E are explanatory drawings showing the operation of the conventional type. Suppose that there are four predictors shown in FIG. 19A. Also, suppose that an image shown in FIG. 19B is input. For simplification, suppose that the input image is a binary image including blank pixels and hatched pixels. Suppose that a pixel equivalent to (x, y)=(0, 0) shown in FIG. 19 is first coded.
FIG. 19C shows the result of output in the conventional type. In a field described as the predictor, the result of predictions is shown. Further, a field at the bottom end shows the output result of the conventional type. In this example, fixed priority is given in the order of a first predictor, a second predictor, a third predictor and a fourth predictor. As run length coding is applied to the output result, output code is as shown in FIG. 19D.
FIG. 19C shows that the predictor D hits on all coordinates. Therefore, in the case of a code shown in FIG. 19E, the quantity of codes can be much reduced. As a result, in the example of prior art, it is known that optimum coding is not executed.
The above problem is caused by mismatch between the priority and the continuity of prediction hit in the conventional type. That is, the fourth predictor which continuously hits in the example shown in FIGS. 19A to E has the lowest priority. A fact that a specific predictor frequently hits before and a fact that the specific predictor continuously hits at the certain time correlate, however, are not necessarily coincident. As only the former has an effect upon priority at this time, the above mismatch may occur.
The above problem is described under supposition that run length coding is applied, however, can be generalized. The more general description of the above problem is that the selection of a predictor is based upon priority for the convenience and selection that enables to reduce the quantity of codes in later coding is not performed.
As described above, the problem of the conventional type is that a predictor is selected based upon the priority, the quantity of codes may be increased, compared with the original quantity of information.
The present invention has been made in view of the above situation and provides a lossless image coding device which can acquire high compression efficiency.
According to an aspect of the present invention, as shown in FIG. 1, the image coding device is provided with an image input part that inputs an image, plural pixel value predictors that predict the value of a target pixel to be coded in the image input by the image input part according to the respective different prediction methods, a prediction error calculator that calculates an error between the actual value of the target pixel in the image input by the above image input part and the predicted value according to the predetermined prediction method, a run counter that judges whether or not the pixel values respectively predicted by the plural pixel value predictors and the value of the target pixel are coincident and counts runs equivalent to the continuous length of coincidences, a selector that selectively outputs either the identification information for identifying the pixel value predictor and the length of its runs or an error calculated by the above prediction error calculator, an encoder that encodes either the identification information and the run length or the error respectively output by the selector according to a predetermined method and an output part that outputs a code encoded by the above encoder. When the run of all pixel value predictors is finished, if there is a run that continued till immediately before and its length is at least 1, the selector outputs the corresponding identification information and its run length, and the run counter initializes holding values. If there is at least one pixel value predictor, in which the predicted value and the value of the target pixel are coincident at that time, the run counter newly starts counting. If there is no such predictor, the selector outputs the error.
According to the above configuration, as a pixel value predictor is selected so that run length is longer, compression ratio can be enhanced.
According to another aspect of the present invention, as shown in FIG. 1 also, an image decoding device is provided with a code input part that inputs a code generated by the above image coding device, a decoder that decodes the code input by the above code input part according to a predetermined method, a selector that selects either of a run executor described later or an prediction error adder based upon information decoded by the above decoder, the run executor that selects one of plural pixel value predictors described later by a frequency equivalent to run length based upon the identification information and run length decoded by the above decoder, the plural pixel value predictors that predict the value of a target pixel according to the respective different methods, a prediction error adder that calculates the value of the target pixel by adding an error decoded by the above decoder to a value predicted by the predetermined method and an image output part, if any of the above pixel value predictors is selected by the above selector and the above run executor, that outputs the value calculated by the selected pixel value predictor, and if not, outputs the value of the target pixel calculated by the prediction error adder.
According to the above configuration, an image coded by above image coding device can be decoded.
According to another aspect of the present invention, an image coding/decoding device includes the above image coding device and the above image decoding device.
According to another aspect of the present invention, as shown in FIG. 10, an image coding device is provided with an image input part that inputs an image, plural pixel value predictors that predict the value of a target pixel to be coded in the image input by the above image input part according to the respective different methods, a prediction error calculator that calculates an error between the value of the target pixel in the image input by the above image input part and a value predicted according to a predetermined method, a high frequency number determiner that judges whether or not each pixel value predicted by the above plural pixel value predictors and the value of the target pixel are coincident and counts the frequency of the coincidence, a selector that judges whether or not each pixel value predicted by the above plural pixel value predictors and the value of the target pixel are coincident and selectively outputs identification information of the above pixel value predictor if coincident and the error calculated by the above prediction error calculator if not, an encoder that encodes the identification information or the error respectively output by the above selector according to a predetermined method and an output part that outputs a code encoded by the above encoder, the frequency of hit predicts is counted by the above high frequency number determiner in first processing and the pixel value predictor is selected based upon high frequency number information determined by the above high frequency number determiner in second processing.
According to another aspect of the present invention, in an image coding method, an image is input, the value of a target pixel to be coded in the image is predicted according to plural different methods, it is judged whether or not each predicted value and the value of the target pixel are coincident or not, if coincidence continues runs are counted for every prediction method equivalent to the coincidence continuous length, when the run of all pixel value predictors is finished, if the length of the longest run that continued till immediately before equals to zero, an error between the actual value of the target pixel and a value predicted according to a predetermined method is coded, and if not, the run length and identification information of the predictor are encoded, a count value of the above runs is initialized, and if at least one of predicted values and the value of the target pixel are coincident, a run count is newly started.
According to another aspect of the present invention, in an image decoding method, a code is input, the above code is decoded according to a predetermined method, it is selected based upon the above decoded information whether a run is to be executed or a prediction error is to be added, if a run is executed, a pixel value is generated by certain prediction method by a frequency based upon decoded identification information and decoded run length, and if not, a pixel value is generated by adding a predicted value according to a predetermined method to a decoded error.
As described above, in the present invention, an image is input, the value of a target pixel to be coded in the input image is predicted according to respective different methods, an error between the actual value of the target pixel and a value predicted according to a predetermined method is calculated, it is judged whether or not the predicted value and the actual value are coincident, if coincident the corresponding identification information or corresponding information and if not the above error is selectively selected, the selected identification information and others or the selected error is encoded according to a predetermined method and further, if there are plural identification information to be selected, the candidates are selected so that the coding of the corresponding predetermined method or the coding of the whole is optimized. The characteristics of not only the priority of prediction but total information are considered by the above method and efficient compression is enabled.